#include "cbigint.h"
#include "cintmath.h"

/**
 * CBigInt - creates big number
 */
CBigInt::CBigInt() : CLinkedList<char>() {
  init(0);
}
//---------------------------------------------------------------------------

/**
 * CBigInt - creates big number from LLS head
 * @param h LLS head
 */
CBigInt::CBigInt(TItem<char>* h) : CLinkedList<char>(h) {
  sign = SIGN_POSITIVE;
}
//---------------------------------------------------------------------------

/**
 * CBigInt - creates big number from string
 * @param str
 */
CBigInt::CBigInt(const char str[]) {
  init(str);
}
//---------------------------------------------------------------------------

/**
 * CBigInt - creates big number from STL string
 * @param str
 */
CBigInt::CBigInt(string str) {
  init(str);
}
//---------------------------------------------------------------------------

/**
 * CBigInt - creates big number from int
 * @param num
 */
CBigInt::CBigInt(int num) {
  init((long) num);
}
//---------------------------------------------------------------------------

/**
 * CBigInt - creates big number from long
 * @param num
 */
CBigInt::CBigInt(long num) {
  init(num);
}
//---------------------------------------------------------------------------

/**
 * CBigInt - copy constructor (deep copy)
 * @param num
 */
CBigInt::CBigInt(const CBigInt &num) {
  copyFrom(num);
  sign = num.getSign();
}
//---------------------------------------------------------------------------

/**
 * init - inits big number from long integer variable
 * @param num
 */
void CBigInt::init(long num) {

  // Reset number
  clear();
  sign = SIGN_POSITIVE;

  // If number is zero, inserts zero, return
  if (num == 0) {
    insertToEnd(0);
    return;
  }

  // Resolve sign of number
  if (num < 0) {
    sign = SIGN_NEGATIVE;
    num = abs(num);
  }

  // Explode number to digits and save them to LLS
  while (num > 0) {
    insertToEnd(num % 10);
    num /= 10;
  }
}
//---------------------------------------------------------------------------

/**
 * init - inits big number from string
 * @param str
 */
void CBigInt::init(string str) {

  // Reset number
  clear();
  sign = SIGN_POSITIVE;
  
  // Iterate through string and save digits
  string::iterator i = str.begin();
  while (i < str.end()) {
    if ((*i) == ord('-')) sign = SIGN_NEGATIVE;
    else insertToBeg((*i) - ord('0'));
    i++;
  }
  deleteRepeatingZeroes();
}
//---------------------------------------------------------------------------

/**
 * operator= - assign given big number (deep copy)
 * @param num
 */
CBigInt& CBigInt::operator = (const CBigInt &num) {
  CLinkedList<char>::operator = (num);
  sign = num.getSign();
  return *this;
}
//---------------------------------------------------------------------------

/**
 * operator+ - adds two big numbers
 * @param num
 * @return sum
 */
CBigInt CBigInt::operator + (const CBigInt &num) const {

  // Resulting sum
  CBigInt result;

  // If signs are different, subtract number which is smaller in abs from
  // number which is greater in abs, result will have sign of greater number
  if (sign != num.getSign()) {

    if (cmpAbs(head, num.getHead()) == ABS_GREATER) {
      result = subAbs(head, num.getHead());
      result.setSign(sign);
    } else {
      result = subAbs(num.getHead(), head);
      result.setSign(num.getSign());
    }
  }
  // If signs are equal, adds given numbers, result sign will remain unchanged
  else {
    result = addAbs(head, num.getHead());
    result.setSign(sign);
  }
  return result;
}
//---------------------------------------------------------------------------

/**
 * operator- - subtract two big numbers
 * @param num
 * @return difference
 */
CBigInt CBigInt::operator - (const CBigInt &num) const {

  // Resulting difference
  CBigInt result;

  // If signs are equal and minuend is greater than subtrahend, result sign
  // will remain same
  // If pokud minuend is smaller than subtrahend, result sign will be inverse
  if (sign == num.getSign()) {

    if (cmpAbs(head, num.getHead()) == ABS_GREATER) {
      result = subAbs(head, num.getHead());
      result.setSign(sign);
    } else {
      result = subAbs(num.getHead(), head);
      result.setSign(sign);
      result.negate();
    }
  }
  // If signs are different, adds minuend and subtrahend, result sign will be
  // same as sign of minuend
  else {
    result = addAbs(head, num.getHead());
    result.setSign(sign);
  }
  return result;
}
//---------------------------------------------------------------------------

/**
 * operator* - multiplies two big numbers
 * @param num big number
 * @return product
 */
CBigInt CBigInt::operator * (const CBigInt &num) const {

  // If factor is equal to 1 respective 0, return this respective 0
  if (CBigInt(1) == num) return *this;
  if (CBigInt(0) == num) return 0;

  // Product
  CBigInt result = mulAbs(head, num.getHead());

  // Result sign will be negation of exclusive disjunction (XOR = ^) of signs
  // of given factors => if signs are different, result will be 0, if signs are
  // same result will be 1
  bool signNXOR = !(sign ^ num.getSign());
  if (signNXOR) result.setSign(SIGN_POSITIVE);
  else result.setSign(SIGN_NEGATIVE);
  return result;
}
//---------------------------------------------------------------------------

/**
 * operator/ - divides two big numbers
 * @param num
 * @return quotient
 */
CBigInt CBigInt::operator / (const CBigInt &num) const {

  // If is divisor equal to 1; -1; 0, return this; -this; 0
  if (CBigInt(1) == num) return *this;
  if (CBigInt(-1) == num) return (*this * -1);
  if (CBigInt(0) == num) return 0;

  // Remainder
  CBigInt remainder;

  // Result of division
  CBigInt res = divAbs(head, num.getHead(), remainder);

  // Result sign will be negation of exclusive disjunction (XOR = ^) of signs
  // of given factors => if signs are different, result will be 0, if signs are
  // same result will be 1
  bool signNXOR = !(sign ^ num.getSign());
  if (signNXOR) res.setSign(SIGN_POSITIVE);
  else res.setSign(SIGN_NEGATIVE);
  return res;
}
//---------------------------------------------------------------------------

/**
 * operator% - modulo operation
 * @param num divisor
 * @return ramainder
 */
CBigInt CBigInt::operator % (const CBigInt &num) const {

  // If ramainder is equal to 1; -1; 0, return
  if (CBigInt(1) == num || CBigInt(-1) == num || CBigInt(0) == num) return 0;

  CBigInt result;
  divAbs(head, num.getHead(), result);
  if (!result.getHead()) result.insertToEnd(0);
  result.setSign(SIGN_POSITIVE);
  return result;
}
//---------------------------------------------------------------------------

/**
 * operator+= - adds given big number to this number
 * @param num
 * @return this
 */
CBigInt& CBigInt::operator += (const CBigInt &num) {
  return *this = *this + num;
}
//---------------------------------------------------------------------------

/**
 * operator-= - subtract given big number from this number
 * @param num
 * @return this
 */
CBigInt& CBigInt::operator -= (const CBigInt &num) {
  return *this = *this - num;
}
//---------------------------------------------------------------------------

/**
 * operator*= - multiplies this number by given big number
 * @param num
 * @return this
 */
CBigInt& CBigInt::operator *= (const CBigInt &num) {
  return *this = *this * num;
}
//---------------------------------------------------------------------------

/**
 * operator/= - divides this number by given big number
 * @param num
 * @return this
 */
CBigInt& CBigInt::operator /= (const CBigInt &num) {
  return *this = *this / num;
}
//---------------------------------------------------------------------------

/**
 * operator>> - simulates bit shift to right (compatibility reasons)
 * @param num
 * @return result of right bit shift
 */
CBigInt CBigInt::operator >> (const CBigInt &num) const {
  return *this / CIntMath<CBigInt>::pow(CBigInt(2), num);
}
//---------------------------------------------------------------------------

/**
 * operator<< - simulates bit shift to left (compatibility reasons)
 * @param num
 * @return result of left bit shift
 */
CBigInt CBigInt::operator << (const CBigInt &num) const {
  return *this * CIntMath<CBigInt>::pow(CBigInt(2), num);
}
//---------------------------------------------------------------------------

/**
 * operator== - compares two big numbers
 * @param num
 * @return true if compared numbers are equal
 */
bool CBigInt::operator == (const CBigInt &num) const {

  TItem<char>* tmpH1 = head;
  TItem<char>* tmpH2 = num.getHead();

  // Compare signs
  if (sign != num.getSign()) return false;

  // Iterate through digits
  while (tmpH1 && tmpH2) {
    // If digits on same positions are not equal, return false
    if (tmpH1->value != tmpH2->value) return false;
    tmpH1 = tmpH1->next;
    tmpH2 = tmpH2->next;
  }

  // If compared numbers have different numbers of digits, return false
  if (tmpH1 || tmpH2) return false;
  return true;
}
//---------------------------------------------------------------------------

/**
 * operator< - compares two big numbers
 * @param num
 * @return true if first number is lesser than second
 */
bool CBigInt::operator < (const CBigInt &num) const {

  // Compare signs
  if (sign == SIGN_POSITIVE && num.getSign() == SIGN_NEGATIVE) return false;
  if (sign == SIGN_NEGATIVE && num.getSign() == SIGN_POSITIVE) return true;
  if (sign == SIGN_NEGATIVE && num.getSign() == SIGN_NEGATIVE) {

    // Compare given numbers in abs
    if (cmpAbs(head, num.getHead()) == ABS_LESSER) return false;
    else return true;
  }

  // Compare given numbers in abs
  if (cmpAbs(head, num.getHead()) == ABS_LESSER) {
    return true;
  } else return false;
}
//---------------------------------------------------------------------------

/**
 * operator> - compares two big numbers
 * @param num
 * @return true if first number is greater than second
 */
bool CBigInt::operator > (const CBigInt &num) const {

  // Compare signs
  if (sign == SIGN_POSITIVE && num.getSign() == SIGN_NEGATIVE) return true;
  if (sign == SIGN_NEGATIVE && num.getSign() == SIGN_POSITIVE) return false;
  if (sign == SIGN_NEGATIVE && num.getSign() == SIGN_NEGATIVE) {

    // Compare given numbers in abs
    if (cmpAbs(head, num.getHead()) == ABS_GREATER) return false;
    else return true;
  }

  // Compare given numbers in abs
  if (cmpAbs(head, num.getHead()) == ABS_GREATER) {
    return true;
  } else return false;
}
//---------------------------------------------------------------------------

/**
 * operator!= - compares two big numbers
 * @param num
 * @return true if numbers are not equal to each other
 */
bool CBigInt::operator != (const CBigInt &num) const {
  return !(*this == num);
}
//---------------------------------------------------------------------------

/**
 * operator>= - compares two big numbers
 * @param num
 * @return true if first number is greater/equal to second
 */
bool CBigInt::operator >= (const CBigInt &num) const {
  return !(*this < num);
}
//---------------------------------------------------------------------------

/**
 * operator<= - compares two big numbers
 * @param num
 * @return true if first number is lesser/equal to second
 */
bool CBigInt::operator <= (const CBigInt &num) const {
  return !(*this > num);
}
//---------------------------------------------------------------------------

/**
 * operator++ - adds one
 * @return this after addition
 */
CBigInt& CBigInt::operator ++ () {
  return *this += CBigInt(1);
}
//---------------------------------------------------------------------------

/**
 * operator-- - subtracts one
 * @return this after subtraction
 */
CBigInt& CBigInt::operator -- () {
  return *this -= CBigInt(1);
}
//---------------------------------------------------------------------------

/**
 * operator++ - adds one
 * @return this before addition
 */
CBigInt CBigInt::operator ++ (int) {
  CBigInt ans(*this);
  *this += CBigInt(1);
  return ans;
}
//---------------------------------------------------------------------------

/**
 * operator-- - subtracts one
 * @return this before subtraction
 */
CBigInt CBigInt::operator -- (int) {
  CBigInt ans(*this);
  *this -= CBigInt(1);
  return ans;
}
//---------------------------------------------------------------------------

/**
 * operator! - checks if number is  equal to zero
 * @return true if number is equal to zero
 */
bool CBigInt::operator ! () const {
  return *this == CBigInt(0);
}
//---------------------------------------------------------------------------

/**
 * operator- - returns negation
 * @return negation
 */
CBigInt CBigInt::operator - () const {
  return *this * CBigInt(-1);
}
//---------------------------------------------------------------------------

/**
 * toString - converts number to string
 * @return string
 */
string CBigInt::toString() const {

  // Output stream, result, LLS head
  ostringstream stream;
  string result = "";
  TItem<char>* tmp = head;

  // Add sign to stream
  if (sign == SIGN_NEGATIVE) stream << "-";

  // Create string
  while (tmp) {
    stream << ord(tmp->value);
    tmp = tmp->next;
  }
  
  // Inverse string
  for (unsigned int i = 0; i < stream.str().length(); i++) {
    result += stream.str()[stream.str().length() - (i + 1)];
  }
  return result;
}
//---------------------------------------------------------------------------

/**
 * getNumOfDigits - returns number of digits
 * @return number of digits
 */
CBigInt CBigInt::getNumOfDigits() {
  TItem<char>* tmpH = head;
  CBigInt count = 0;
  while (tmpH) {
    count++;
    tmpH = tmpH->next;
  }
  return count;
}
//---------------------------------------------------------------------------

/**
 * toNumberSystem - converts number to given number system
 * @param nSystem number of digits in destination number system
 * @return number in system nSystem
 */
CBigInt CBigInt::toNumberSystem(unsigned short nSystem) {

  CBigInt result, tmpNum(*this);
  result.clear();

  // Subsequently division of number by destination number system base
  while (tmpNum > 0) {
    CBigInt tmpResult(tmpNum % nSystem);

    // Isolate discrete digits
    CBigInt tmpRank = 10;
    while (tmpRank < nSystem) {
      if (tmpResult < tmpRank) tmpResult.insertToEnd(0);
      tmpRank.insertToBeg(0);
    }
    result.insertListToEnd(tmpResult);
    tmpNum = tmpNum / nSystem;
  }
  return result;
}
//---------------------------------------------------------------------------

/**
 * addAbs - adds two big numbers in abs
 * @param h1
 * @param h2
 * @return sum
 */
CBigInt CBigInt::addAbs(TItem<char>* h1, TItem<char>* h2) const {

  // Result of addition, temporary carry
  CBigInt result;
  short carry = 0;

  // Set result to zero
  result.clear();

  // Iterate through digits of both numbers
  while (h1 || h2) {
    short tmpSum = carry;

    // If position is not at the end of addend, adds actual digit to sum and
    // move to next digit
    if (h1) {
      tmpSum += h1->value; h1 = h1->next;
    }
    if (h2) {
      tmpSum += h2->value; h2 = h2->next;
    }

    // Calculate carry and new digit of result
    result.insertToEnd(tmpSum % 10);
    carry = tmpSum / 10;
  }

  // If carry is non-zero join it to result
  if (carry) result.insertToEnd(carry);
  return result;
}
//---------------------------------------------------------------------------

/**
 * subAbs - subtracts two big numbers in abs (condition h1 >= h2)
 * @param h1
 * @param h2
 * @return difference
 */
CBigInt CBigInt::subAbs(TItem<char>* h1, TItem<char>* h2) const {

  // Result of subtraction, temporary carry
  CBigInt result;
  short carry = 0;

  // Set result to zero
  result.clear();

  // Iterate through digits of both numbers till position reaches end of
  // minuend
  while (h1) {

    // Saves actual digit of subtrahend
    short tmpValue = h2 ? h2->value : 0;

    // Subtract digits
    short tmpDif = h1->value - (tmpValue + carry);

    // If result of subtraction is negative (greater digit was subtracted from
    // lesser digit), increases result of subtraction by 10 and set carry to 1
    // In other case carry is 0
    if (tmpDif < 0) {
      tmpDif += 10;
      carry = 1;
    } else {
      carry = 0;
    }

    // Saves digit and move to another
    result.insertToEnd(tmpDif);
    h1 = h1->next;
    if (h2) h2 = h2->next;
  }

  // Deletes zeros from the beginning of number
  result.deleteRepeatingZeroes();
  return result;
}
//---------------------------------------------------------------------------

/**
 * mulAbs - multiplies two big numbers in abs
 * @param h1
 * @param h2
 * @return product
 */
CBigInt CBigInt::mulAbs(TItem<char>* h1, TItem<char>* h2) const {

  // Product, temporary margin
  CBigInt result(0), margin;
  margin.clear();

  // Iterate through digits of second factor
  while (h2) {

    // Sets pointer to head of first factor, temporary carry
    TItem<char>* tmpH1 = h1;
    int carry = 0;

    // Partial result
    CBigInt parcRes;
    parcRes.clear();

    // Iterate through digits of first factor and multiply them with actual
    // digit of second factor
    while (tmpH1) {

      // Temporary product
      int tmpMul = h2->value * tmpH1->value + carry;

      // Calculate new digit of partial result and carry
      parcRes.insertToEnd(tmpMul % 10);
      carry = tmpMul / 10;

      // Move to next digit
      tmpH1 = tmpH1->next;
    }

    // If carry is non-zero join it to partial result, align partial result
    // with margin
    if (carry) parcRes.insertToEnd(carry);
    parcRes.insertListToBeg(margin);

    // Add partial result to global result (product)
    result += parcRes;

    // Increase margin and move to next digit of second factor
    margin.insertToEnd(0);
    h2 = h2->next;
  }

  // Deletes zeros from beginning of result number
  result.deleteRepeatingZeroes();
  return result;
}
//---------------------------------------------------------------------------

/**
 * divAbs - divides two big numbers in abs
 * @param h1
 * @param h2
 * @param r
 * @return quotient
 */
CBigInt CBigInt::divAbs(TItem<char>* h1, TItem<char>* h2, CBigInt &r) const {

  // Temporary dividend1, dividend2, result of division
  CBigInt tmpD1(h1), tmpD2, result;
  result.clear();
  tmpD2.clear();

  // While temporary dividend1 has non-zero value (has digits)
  while (tmpD1.getHead()) {

    // Insert to temporary dividend2 greatest (most left) digit of dividend1
    // and delete this digit form dividend2
    tmpD2.insertToBeg(tmpD1.findTail()->value);
    tmpD1.removeFromEnd();

    // Divide dividend2 by divisor, insert integer result of division to
    // result, save remain to dividend2
    CBigInt d = divSAbs(tmpD2.getHead(), h2, tmpD2);
    result.insertListToBeg(d);

    // Prevent zero in most left digit of dividend2
    if (tmpD2 == 0) tmpD2.clear();
  }

  // Delete zeros from beginning of number
  result.deleteRepeatingZeroes();
  r = tmpD2;
  return result;
}
//---------------------------------------------------------------------------

/**
 * divSAbs - divides two big numbers in abs (slow)
 * @param h1
 * @param h2
 * @param r
 * @return quotient
 */
CBigInt CBigInt::divSAbs(TItem<char>* h1, TItem<char>* h2, CBigInt &r) const {

  // If dividend is lesser than divisor, result will be 0
  if (cmpAbs(h1, h2) == ABS_LESSER) return 0;

  // Result of division, temporary difference
  CBigInt result(0), tmpDiv(h1);

  // While dividend is greater than divisor (in abs), subtract divisor from
  // dividend
  // Result is number of subtractions, remain is remaining value of dividend
  while (cmpAbs(tmpDiv.getHead(), h2) != ABS_LESSER) {
    tmpDiv = subAbs(tmpDiv.getHead(), h2);
    result++;
  }
  r = tmpDiv;
  return result;
}
//---------------------------------------------------------------------------

/**
 * cmpAbs - compare two big numbers in abs
 * @param h1
 * @param h2
 * @return ABS_EQUAL, ABS_GREATER (first > second), ABS_LESSER (first < second)
 */
int CBigInt::cmpAbs(TItem<char>* h1, TItem<char>* h2) const {

  int eSign = ABS_EQUAL;

  // Iterate through all digits (number is represented in reverse order)
  while (h1 && h2) {

    // If corresponding digits are not equal, saves status
    if (h1->value > h2->value) eSign = ABS_GREATER;
    else if (h1->value < h2->value) eSign = ABS_LESSER;
    h1 = h1->next;
    h2 = h2->next;
  }

  // If numbers has different number of digits, number with large amount of
  // digits is greater (in abs)
  if (h1) eSign = ABS_GREATER;
  if (h2) eSign = ABS_LESSER;
  return eSign;
}
//---------------------------------------------------------------------------

/**
 * deleteRepeatingZeroes - deletes zeros from beginning of number (end of LLS)
 */
void CBigInt::deleteRepeatingZeroes() {

  TItem<char>* tmp = head;
  TItem<char>* lastNum = head;

  // Find first non-zero digit (last LLS)
  while (tmp) {
    if (tmp->value != 0) lastNum = tmp;
    tmp = tmp->next;
  }

  // Deletes LLS from the position of found digit
  tmp = lastNum->next;
  lastNum->next = NULL;

  while (tmp) {
    TItem<char>* prev = tmp;
    tmp = tmp->next;
    delete prev;
  }
}
//---------------------------------------------------------------------------

/**
 * negate - negates big number
 */
void CBigInt::negate() {

  // If is number zero, return
  if (*this == 0) return;

  // Change sign
  if (sign == SIGN_POSITIVE) sign = SIGN_NEGATIVE;
  else sign = SIGN_POSITIVE;
}
//---------------------------------------------------------------------------

/**
 * free - deletes big number
 */
void CBigInt::free() {
  CLinkedList<char>::free();
  sign = SIGN_POSITIVE;
}
//---------------------------------------------------------------------------

/**
 * getSign - returns sign of big number
 * @return sign
 */
int CBigInt::getSign() const {
  return sign;
}
//---------------------------------------------------------------------------

/**
 * setSign - sets sign of big number
 * @param sign
 */
void CBigInt::setSign(int sign) {
  this->sign = sign;
}
//---------------------------------------------------------------------------

/**
 * longValue - converts big number to long
 * @return value in long
 */
long CBigInt::longValue() const {
 
  TItem<char>* tmp = head;
  long result = 0, rank = 1;
  
  while (tmp) {
  	result += tmp->value * rank;
  	rank *= 10;
    tmp = tmp->next;
  }
  return result;
}
//---------------------------------------------------------------------------
